package com.zxy.javaarithmetic.chapter_2_LinkList;

/*
 *  @项目名：  study
 *  @包名：    com.zxy.javaarithmetic.chapter_2_LinkList
 *  @文件名:   P_6_JosephProblem
 *  @创建者:   zhangxy
 *  @创建时间:  2018/12/10 16:54
 *  @描述：    环形单链表的约瑟夫问题
 */
public class P_6_JosephProblem {

	public static void main(String[] args) {
		Node head = LinkListUtils.getRingNode(7);
		LinkListUtils.printRingNode(head);
		LinkListUtils.printRingNode(josephusKillM2(head, 3));
	}


	//时间复杂度 O(nm)
	private static Node josephusKillM1(Node head, int m) {
		if (head == null || head.next == head || m < 1) {
			return head;
		}
		int count = 0;
		while (head.next != head) {
			count++;
			if ((count + 1) == m) {
				head.next = head.next.next;
				count = 0;
			}
			head = head.next;
		}
		return head;
	}

	/**
	 * 时间复杂度O(N)，额外空间复杂度O(1)
	 * @param head
	 * @param m  编号m,要删除的节点
	 * @return
	 */
	private static Node josephusKillM2(Node head, int m) {
		if (head == null || head.next == null) {
			return head;
		}
		int len = 1;
		Node cur = head.next;
		while (cur != head) {
			len++;
			cur = cur.next;
		}
		int liveIndex = getLive(len, m);
		//		System.out.println("liveindex="+liveIndex);
		while (--liveIndex != 0) {
			head = head.next;
		}
		//删除其他所有节点
		head.next = head;
		return head;
	}

	//获取最终剩下的节点在原链表中的位置
	private static int getLive(int len, int m) {
		if (len == 1) {
			return 1;
		}
		return (getLive(len - 1, m) + m - 1) % len + 1;
	}
}
